An essential semiconductor device is a semiconductor memory, such as a random access memory (RAM) device. A RAM allows a memory circuit to execute both read and write operations on its memory cells. Typical examples of RAM devices include dynamic random access memory (DRAM) and static random access memory (SRAM).
Another form of memory is the content addressable memory (CAM) device. A conventional CAM is viewed as a static storage device constructed of modified RAM cells. A CAM is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data in a comparand register) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers, gateways and switches, computer systems and other devices that require rapid content searching, such as routing data or tables for data networks or matching URLs. The CAM words are loaded into the CAM by a system controller. These fixed tables reside in the CAM for a relatively long period of time. A word in a CAM is typically large and can be 96 bits or more.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., DRAM and SRAM). For example, data is stored in a RAM in a particular location, called an address. During a memory access, the user supplies an address and reads or writes the data at the specified address. Every memory storage location contains a match word part and additional data associated with each match word, such as an output port routing index in a network. It may also store a bit to indicate whether the match word participates in the networking process.
Once information is stored in a memory storage location, it is located by comparing every bit stored in the match word part with data in a comparand register. When the contents stored in the CAM match word do not match the data in the comparand register, a local match detection circuit returns a “mismatch” indication. When the contents stored in the CAM match word match the data in the comparand register, the local match detection circuit returns a “match” indication. If one or more local match detect circuits return a match indication, the CAM device returns a “match” indication. Otherwise, the CAM device returns a “no-match” indication, usually with a priority encoding scheme to return the address of the most desirable match and it associated data. The most desirable match may be the highest address or the lowest address in the CAM device. If the CAM match word does not match the data in the comparand register, then the CAM device returns a “mismatch” indication. In addition, the CAM may return the identification of the address/memory storage location in which the desired data is stored or one of such addresses, such as a highest priority match address, if more than one corresponding CAM storage location contained matching data. Thus, with a CAM, the user supplies the data and receives the address if a match is found in memory.
For high CAM look-up throughput rates, the incoming data is compared with all CAM entries in parallel, resulting in high power consumption. In some power saving schemes, individual entries can be programmed to never match, or banks of entries can be enabled or disabled.
TCAMs are similar to CAMs except that each bit can also be programmed to match a ‘don't care’ or X value. When an incoming TCAM data word is compared with an entry, each match bit in an entry can be programmed to be one of a (0,1,X), where X is a ‘don't care’ match value that matches a 0 or 1 in the corresponding bit on the incoming TCAM word. Of course, all the other bits in a word have to match according to the (0,1,X) pattern before a TCAM word match occurs. For example, programming a TCAM entry with all X's causes the entry to match all possible inputs.
With each CAM or TCAM word match, time consuming electrical events occur. The first event is the pre-charging of each match line associated with a CAM storage location to indicate a match. Then the match between the bits of the incoming word/comparand and the bits of each CAM storage location occurs. If even only one CAM bit in the comparand fails to match a corresponding bit in a CAM entry, then the corresponding match line is discharged to indicate a mismatch at that entry. A match line is typically connected to many match circuits, so is relatively long and has significant wire and circuit loading capacitance. If M bits in a CAM word don't match the comparand, then the match line is discharged through M circuits, each able to drain a certain amount of current. If M=1, then the discharge is the slowest mismatch case. The resulting match voltage level is then sampled at a safe time for this worst-case discharge timing to occur. As a result, a CAM is relatively slow memory device.